package com.luoc;

import com.google.protobuf.StringValue;
import com.sun.org.apache.xpath.internal.operations.Bool;

import javax.swing.text.StyledEditorKit;
import java.lang.management.BufferPoolMXBean;
import java.math.BigInteger;
import java.sql.SQLOutput;
import java.util.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Test {
    //字符串最后一个单词的长度
   /* public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (scan.hasNext()) { // 注意 while 处理多个 case
            String str = scan.nextLine();
            System.out.println(lengthOfLast(str));
        }
    }

    public static int lengthOfLast(String str){
        String[] strArr = str.split(" ");
        return strArr[strArr.length - 1].length();
    }*/

    // 注意类名必须为 Main, 不要有任何 package xxx 信息

  /*  public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        String tar = bf.readLine();
        if(null != str && null != tar){
            System.out.print(str.length() - str.toLowerCase().replace(tar.toLowerCase(),"").length());
        }

    }*/
  /*public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      Set<String> hashSet = new HashSet();
      String str;
      if((str = br.readLine()) != null){
          hashSet.add(str);
      }

      String[] strArr = hashSet.toArray(new String[0]);Arrays.sort();
  }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String str = in.nextLine();

        while (str.length() != 0) {
            if (str.length() <= 8) {
                System.out.println((str + "00000000").substring(0, 8));
                break;
            } else {
                System.out.println(str.substring(0, 8));
                str = str.substring(8);
            }
        }
    }*/

    // 十六进制转换为十进制
    /*public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String str = in.nextLine();
            if(null != str){
                System.out.println(Long.parseLong(str.substring(2),16));
            }
        }

    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int total = in.nextInt();
        Map<Integer, Integer> hmap = new HashMap();
        for (int i = 0; i < total; i++) {
            int key = in.nextInt();
            int value = in.nextInt();
            if (null != hmap && hmap.keySet().contains(key)) {
                value += hmap.get(key);
            }
            hmap.put(key, value);
        }
        Integer[] keyArr = hmap.keySet().toArray(new Integer[hmap.keySet().size()]);
        for (int key :) {
            System.out.println(key + " " + hmap.get(key));

        }
    }
*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        long l = Long.parseLong(input, 2);
        System.out.println("l:"+l);
    }*/
    /*public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int[] count = new int[7];
        String in;
        while ((in = bf.readLine()) != null) {
            //以~分隔
            String[] split = in.split("~");
            String ip = split[0];//获取IP地址
            String mask = split[1];//获取子网掩码

            String[] ips = ip.split("\\.");
            int num1 = 0;
            int num2 = 0;
            try {
                num1 = Integer.parseInt(ips[0]);
                num2 = Integer.parseInt(ips[1]);
                Integer.parseInt(ips[2]);
                Integer.parseInt(ips[3]);
            } catch (NumberFormatException e) {
                count[5]++;
                continue;
            }


            //1、先判IP地址是否合法
            boolean isIP = isIP(ip);
            boolean isMask = isMask(mask);
            //如果IP和子网掩码都合法 就判断是哪种类型的IP地址
            if (isIP && isMask) {
                count = countIP(ip, count);
            } else if ((isIP == false || isMask == false) && num1 != 127 && num1 != 0) {
                count[5]++;
            }
        }
        for (int i = 0; i < 6; i++)
            System.out.print(count[i] + " ");
        System.out.print(count[6]);
    }

    //判断IP是否合法
    public static boolean isIP(String IP) {
        //1. 类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时可以忽略
        String[] IParr = IP.split("\\.");
        Boolean isTrue = true;
        for (int i = 0; i < IParr.length; i++) {
            if (IParr[i].length() <= 0 || IParr[i] == "") {//非法判断
                isTrue = false;
            }
        }
        return isTrue;
    }

    //判断子网掩码是否合法
    public static boolean isMask(String mask) {
        String[] maskarr = mask.split("\\.");
        boolean result = false;
        //0000 0000~ 1111 1110 八位
        //子网掩码为二进制下前面是连续的1，然后全是0。（例如：255.255.255.32就是一个非法的掩码）
        // 注意二进制下全是1或者全是0均为非法
        int[] maskRange = {254, 252, 248, 240, 224, 192, 128, 0};
        List<Integer> list = new ArrayList();
        for (int i : maskRange)
            list.add(i);
        //255.255.255.
        if ("255".equals(maskarr[0]) && "255".equals(maskarr[1]) && "255".equals(maskarr[2])) {
            if (list.contains(Integer.parseInt(maskarr[3]))) {
                result = true;
            }
        }
        //255.255.
        else if ("255".equals(maskarr[0]) && "255".equals(maskarr[1])) {
            if (list.contains(Integer.parseInt(maskarr[2])) && "0".equals(maskarr[3])) {
                result = true;
            }
        }
        //255.
        else if ("255".equals(maskarr[0])) {
            if (list.contains(Integer.parseInt(maskarr[1])) && "0".equals(maskarr[2]) && "0".equals(maskarr[3])) {
                result = true;
            }
        } else if (list.contains(Integer.parseInt(maskarr[0]))) {
            if ("0".equals(maskarr[1]) && "0".equals(maskarr[2]) && "0".equals(maskarr[3])) {
                result = true;
            }
        }
        return result;
    }//method end

    //私有IP判断
    *//*10.0.0.0-10.255.255.255  172.16.0.0-172.31.255.255  192.168.0.0-192.168.255.255*//*
    public static boolean isPrivateIP(String IP) {
        String[] split = IP.split("\\.");
        //根据范围即可
        if (Integer.parseInt(split[0]) == 10) return true;
        else if (Integer.parseInt(split[0]) == 172 && (Integer.parseInt(split[1]) > 15 && Integer.parseInt(split[1]) < 32)) {
            return true;
        } else if (Integer.parseInt(split[0]) == 192 && Integer.parseInt(split[1]) == 168) {
            return true;
        } else {
            return false;
        }
    }

    //各类ip计数
    public static int[] countIP(String IP, int[] count) {
        String[] split = IP.split("\\.");
        int first = Integer.parseInt(split[0]);
        //如果是私有ip
        if (isPrivateIP(IP)) count[6]++;

        //判断其他地址范围
*//*        A类地址1.0.0.0~126.255.255.255;
        B类地址128.0.0.0~191.255.255.255;
        C类地址192.0.0.0~223.255.255.255;
        D类地址224.0.0.0~239.255.255.255；
        E类地址240.0.0.0~255.255.255.255*//*
        if (first >= 1 && first <= 126)
            count[0]++;
        else if (first >= 128 && first <= 191)
            count[1]++;
        else if (first >= 192 && first <= 223)
            count[2]++;
        else if (first >= 224 && first <= 239)
            count[3]++;
        else if (first >= 240 && first <= 255)
            count[4]++;
        return count;
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] input ;
        String[] tempArr;
        String temp;
        Map<String, Integer> name = new HashMap<>();
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            temp = in.nextLine();
            tempArr = temp.split("\\\\");
            input = tempArr[tempArr.length - 1].split(" ");
            if (input[0].length() > 16) {
                input[0] = input[0].substring(input[0].length() - 16);
            }
            //判断文件名和错误行数是否重复
            if (!name.keySet().contains(input[0] + "," + input[1]) ) {
                name.put(input[0] + "," + input[1], 1);
            } else {
                //错误日志重复记录重复次数
                name.put(input[0] + "," + input[1],name.get(input[0] + "," + input[1]) + 1);
            }

        }

        String[] nameArr = new String[name.size()];
        String[] nameLine ;
        if (nameArr.length < 9) {
            for (String str : nameArr) {
                nameLine = str.split(",");
                System.out.println(nameLine[0] + " " + nameLine[1] + " " + name.get(str));
            }
        } else {
            for (int i = (nameArr.length - 8); i < nameArr.length; i ++) {
                nameLine = nameArr[i].split(",");
                System.out.println(nameLine[0] + " " + nameLine[1] + " " + name.get(nameArr[i]));
            }
        }

    }*/
    //lambda表达式实例
    /*public static void main(String[] args) {
        List<String> list = Arrays.asList("AAa","bbb","aab","Aab");
        //循环打印字符串
        //list.forEach(System.out::println);
        //list.forEach(s -> System.out.println(s));
        //数组排序
        *//*list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });*//*
        //list.sort((o1,o2) ->o1.compareTo(o2));
        Collections.sort(list,(o1,o2) ->o1.toUpperCase().compareTo(o2.toUpperCase()));
        list.forEach(System.out::println);
    }*/


    /*public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            System.out.println(mergeAndSortChange(str1, str2));
        }


    }

    //对字符串进行 1前后合并 2排序 3指定字符转换
    public static String mergeAndSortChange(String str1, String str2) {
        //1.合并
        String str = str1 + str2;
        //2.排序
        ArrayList<Character> list1 = new ArrayList<>();//存放偶数位字符
        ArrayList<Character> list2 = new ArrayList<>();//存放奇数位字符
        for (int i = 0; i < str.length(); i++) {
            if (i % 2 == 0) {
                list1.add(str.charAt(i));
            } else {
                list2.add(str.charAt(i));
            }
        }
        Collections.sort(list1);
        Collections.sort(list2);
        //重新拼接
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < list1.size(); i++) { //list1.size()>=list2.size()
            builder.append(list1.get(i));
            if (i <= list2.size() - 1) { //防止越界
                builder.append(list2.get(i));
            }
        }
        //3.对字符进行转换操作
        for (int i = 0; i < builder.length(); i++) {
            String s = builder.substring(i, i + 1);
            if (s.matches("[0-9a-fA-F]")) {
                //把16进制转成10进制，再转成二进制
                StringBuilder binary = new StringBuilder(Integer.toBinaryString(
                        Integer.parseInt(s, 16)));
                int len = binary.length();
                for (int j = 0; j < 4 - len ; j++) { //补零
                    binary.insert(0, "0");
                }
                binary = binary.reverse();//翻转
                int n = Integer.parseInt(binary.toString(), 2); //把二进制转成10进制
                String hexString = Integer.toHexString(
                        n).toUpperCase();//转成16进制字符串大写
                builder.replace(i, i + 1, hexString); //替换
            }
        }
        return builder.toString();

    }*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String input = in.nextLine();
        if (input.length() < 10000) {
            for (int i = 0; i < input.length(); i++) {
                String s = String.valueOf(input.charAt(i));
                if (s.matches("[^0-9A-Za-z]")) {
                    input = input.replace(s, ",");
                }
            }
            String[] strArr = input.split(",");
            for (int i = strArr.length - 1; i >= 0; i--) {
                System.out.print(strArr[i] +" ");
            }
        }

    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        if (null != input && input.length() == 1) {
            System.out.println(1);
        } else {
            int max = Integer.MIN_VALUE;
            char inAr[] = input.toCharArray();
            for (int i = 0; i < inAr.length; i++) {
                for (int j = i + 1; j < inAr.length; j++) {
                    if (inAr[i] == inAr[j]) {
                        max = Math.max(getLongCodeStr(i, j, inAr),max);
                    }
                }
            }
            System.out.println(max);
        }

    }
    public static int getLongCodeStr(int begin, int end, char[] inAr) {
        int a = (end - begin)+1;
        for (; end - begin > 0;) {
            if (inAr[begin] == inAr[end]) {
                begin++;
                end--;
            } else {
                return 0;
            }
        }

        return a;

    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] ipArr = in.nextLine().split("\\.");
        String num = in.nextLine();
        StringBuilder sb = new StringBuilder();
        //ip转long型10进制数字
        for (String str : ipArr) {
            StringBuilder binaryString = new StringBuilder(Integer.toBinaryString(Integer.parseInt(str)));
            int le = binaryString.length();
            for (int i = 0; i < 8 - le; i++) {
                binaryString.insert(0, "0");
            }
            sb.append(binaryString);
        }
        System.out.println(Long.parseLong(sb.toString(), 2));

        //10进制数字转ip
        StringBuilder sb2 = new StringBuilder(Long.toBinaryString(Long.parseLong(num)));
        String res = "";
        int le2 = sb2.length();
        //缺失位数添0补足32位
        for (int i = 0; i < 32 - le2; i++) {
            sb2.insert(0, "0");
        }
        //拆分为4部分ip格式
        for (int i = 0; i < sb2.length() - 1; i += 8) {
            String str = sb2.substring(i, i + 8);
            int a = Integer.parseInt(str, 2);
            res += a + ".";
        }
        System.out.println(res.substring(0, res.length() - 1));


    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        List<String> nums = new ArrayList<>();
        List<String> letters = new ArrayList<>();
        for(int i = 0; i < input.length(); i++){
            String s = input.substring(i,i + 1);
            if(s.matches("[0-9]")){
                nums.add(s);
            }
            if(s.matches("[a-zA-Z]")){
                letters.add(s);
            }
        }
        Collections.sort(nums);
        Collections.sort(letters);
        nums.addAll(letters);
        for (String num : nums) {
            System.out.println(num);
        }
    }*/

    /*
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                int num = in.nextInt();
                solution(num);
            }
        }

        private static void solution(int num) {
            StringBuilder res = new StringBuilder();
            int[][] arr = new int[num][num];
            int count = 1;
            for(int i = 0; i < num; i++) {
                // 从左下到右上的斜顺序构造数组
                for(int j = i; j >= 0; j--) {
                    arr[j][i - j] = count++;
                }
            }
            // 封装结果
            for(int i = 0; i < arr.length; i++) {
                // 只需要遍历非0的元素
                for(int j = 0; j < arr.length - i; j++) {
                    res.append(arr[i][j] + " ");
                }
                // 对每一行最后添加换行符
                if(i != num - 1) {
                    res.append("\n");
                }
            }
            System.out.println(res);
        }
     */
   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        StringBuilder sb = new StringBuilder();
        StringBuilder res = new StringBuilder();
        Set<String> set = new LinkedHashSet<>();
        String letters = "abcdefghijklmnopqrstuvwxyz";
        String useletter = letters;
        for(int i=0; i<s.length();i++){
            String temp = s.substring(i,i+1);
            set.add(temp);
        }

        for (String string : set) {
           sb.append(string);
            useletter = useletter.replace(string, "");
        }
        sb.append(useletter);
        for(int i=0; i<t.length();i++){
            String temp = t.substring(i,i+1);
            int a = letters.indexOf(temp);
            res.append(sb.charAt(a));
        }
        System.out.println(res.toString());


    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double h = in.nextInt();
        double htotal = 0;
        for(int i = 0; i < 5; i++){
            htotal += h + h/2.0;
            h = h/2;
        }
        System.out.println(htotal - h +"\n"+h);
    }*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String mask = in.nextLine();
            String ip1 = in.nextLine();
            String ip2 = in.nextLine();
            if (!isIP(ip1) || !isIP(ip2) || !isMask(mask)) {
                System.out.println(1);
            } else if ((changeIpFormat(mask) & changeIpFormat(ip1)) == (changeIpFormat(mask) & changeIpFormat(ip2))) {
                System.out.println(0);
            } else {
                System.out.println(2);
            }

        }
    }

    */

    /**
     * 将ip格式转化为二进制格式
     *
     * @param mask
     * @param ip1
     * @param ip2
     * @return
     *//*
    public static long changeIpFormat(String str) {
        String[] strarr = str.split("\\.");
        StringBuilder strfull = new StringBuilder();
        for (String s : strarr) {
            StringBuilder strb = new StringBuilder(Integer.toBinaryString(Integer.parseInt(s)));
            int length = strb.length();
            for (int i = 0; i < 8 - length; i++) {
                strb.insert(0, 0);
            }
            strfull.append(strb);
        }
        return Long.parseLong(strfull.toString(), 2);
    }

    //判断IP是否合法
    public static boolean isIP(String IP) {
        //1. 类似于【0.*.*.*】和【127.*.*.*】的IP地址不属于上述输入的任意一类，也不属于不合法ip地址，计数时可以忽略
        String[] IParr = IP.split("\\.");
        Boolean isTrue = true;
        for (int i = 0; i < IParr.length; i++) {
            if (IParr[i].length() <= 0 || IParr[i] == "" || Integer.parseInt(IParr[i]) > 255 || Integer.parseInt(IParr[i])<0) {//非法判断
                isTrue = false;
            }
        }
        return isTrue;
    }

    //判断子网掩码是否合法
    public static boolean isMask(String mask) {
        String[] maskarr = mask.split("\\.");
        boolean result = false;
        //0000 0000~ 1111 1110 八位
        //子网掩码为二进制下前面是连续的1，然后全是0。（例如：255.255.255.32就是一个非法的掩码）
        // 注意二进制下全是1或者全是0均为非法
        int[] maskRange = {254, 252, 248, 240, 224, 192, 128, 0};
        List<Integer> list = new ArrayList();
        for (int i : maskRange)
            list.add(i);
        //255.255.255.
        if ("255".equals(maskarr[0]) && "255".equals(maskarr[1]) && "255".equals(maskarr[2])) {
            if (list.contains(Integer.parseInt(maskarr[3]))) {
                result = true;
            }
        }
        //255.255.
        else if ("255".equals(maskarr[0]) && "255".equals(maskarr[1])) {
            if (list.contains(Integer.parseInt(maskarr[2])) && "0".equals(maskarr[3])) {
                result = true;
            }
        }
        //255.
        else if ("255".equals(maskarr[0])) {
            if (list.contains(Integer.parseInt(maskarr[1])) && "0".equals(maskarr[2]) && "0".equals(maskarr[3])) {
                result = true;
            }
        } else if (list.contains(Integer.parseInt(maskarr[0]))) {
            if ("0".equals(maskarr[1]) && "0".equals(maskarr[2]) && "0".equals(maskarr[3])) {
                result = true;
            }
        }
        return result;
    }//method end*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        int[] arr = new int[4];
        for(int i= 0; i < input.length();i++){
            String temp = input.substring(i,i+1);
            if(temp.matches("[a-zA-Z]")){
                arr[0] +=1;
            }
            else if(temp.equals(" ")){
                arr[1] +=1;
            }
            else if(temp.matches("[0-9]")){
                arr[2] +=1;
            }
            else {
                arr[3] +=1;
            }
        }
        for (int s : arr) {
            System.out.println(s);
        }
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int h = in.nextInt();
        int w = in.nextInt();
        int[][] mg = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                mg[i][j] = in.nextInt();
            }
        }
        dfs(mg, h - 1, w - 1);
    }

    private static boolean dfs(int[][] mg, int h, int w) {
        if (h < 0 || h > mg.length - 1 || w < 0 || w > mg[h].length - 1) {
            return false;
        }
        int temp = mg[h][w];
        mg[h][w] = 1;
        if ((h == 0 && w == 0) || dfs(mg, h - 1, w) || dfs(mg, h, w - 1)
                || dfs(mg, h + 1, w) || dfs(mg, h, w + 1)) {
            System.out.println("(" + h + "," + w + ")");
            return true;
        }
        mg[h][w] = temp;
        return false;
    }*/
    /*public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String line = sc.nextLine();
            line = line.replaceAll("\\{", "(");
            line = line.replaceAll("}", ")");
            line = line.replaceAll("\\[", "(");
            line = line.replaceAll("]", ")");
            System.out.println(resolve(line));
        }
        sc.close();
    }

    private static int resolve(String line) {
        char[] chars = line.toCharArray();
        int length = chars.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int number = 0;
        char sign = '+';
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            if (c == ' ') {
                continue;
            }
            if (Character.isDigit(c)) {
                number = number * 10 + c - '0';
            }
            if (c == '(') {
                int j = i + 1;
                int count = 1;
                while (count > 0) {
                    if (chars[j] == ')') {
                        count--;
                    }
                    if (chars[j] == '(') {
                        count++;
                    }
                    j++;
                }
                number = resolve(line.substring(i + 1, j - 1));
                i = j - 1;
            }
            if (!Character.isDigit(c) || i == length - 1) {
                if (sign == '+') {
                    stack.push(number);
                } else if (sign == '-') {
                    stack.push(-1 * number);
                } else if (sign == '*') {
                    stack.push(stack.pop() * number);
                } else if (sign == '/') {
                    stack.push(stack.pop() / number);
                }
                sign = c;
                number = 0;
            }
        }
        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }*/

    /*public static void main(String[] args) throws ScriptException {
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        input = input.replace("[", "(");
        input = input.replace("]", ")");
        input = input.replace("{", "(");
        input = input.replace("}", ")");
        // 利用java执行Script语句
        ScriptEngineManager scriptEngineManager = new ScriptEngineManager();
        ScriptEngine engine = scriptEngineManager.getEngineByName("nashorn");
        System.out.println(engine.eval(input));
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String count = in.nextLine();
            String[] strArr = in.nextLine().split(" ");
            int index = Integer.parseInt(in.nextLine());
            System.out.println(strArr[strArr.length - index ]);
        }
    }*/

    // 四则运算
   /* public class Main {
        public static void main(String[] args) throws ScriptException {
            Scanner scan = new Scanner(System.in);
            String input = scan.nextLine();
            input = input.replace("[", "(");
            input = input.replace("]", ")");
            input = input.replace("{", "(");
            input = input.replace("}", ")");
            // 利用java执行Script语句
            ScriptEngineManager scriptEngineManager = new ScriptEngineManager();
            ScriptEngine engine = scriptEngineManager.getEngineByName("nashorn");
            System.out.println(engine.eval(input));
        }
    }*/


    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] input = in.nextLine().split(",");
        for (int i= 0; i <input.length;i++){
            if(input[i].equals("...")){
                System.out.println(Integer.parseInt(input[i+1]) - Integer.parseInt(input[i-1]) );
            }

        }
    }
*/


    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int count = 0;
        for (int i = 0; i <= num ; i++){
            if(num % 7 == 0 || String.valueOf(num).contains("7")){
                count++;
            }
        }
        System.out.println(count);
    }*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int count = 0;
        for (int i = 1; i < num; i++){
            if (isWqnum(i)){
                count++;
            }
        }
        System.out.println(count);
    }

    public static boolean isWqnum(int a){
        boolean flag = false;
        List<Integer> list = new ArrayList<>();
        for(int i = 2; i < Math.sqrt(a); i++){
            if(a % i == 0){
                int num = a / i;
                if (!list.contains(i)){
                    list.add(i);
                }if (!list.contains(num)){
                    list.add(num);
                }
            }
        }
        if(list.stream().reduce(0,(o1,o2) -> o1+o2) == a){
            flag = true;
        }

        return flag;*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger a = new BigInteger(in.nextLine());
        BigInteger b = new BigInteger(in.nextLine());
        System.out.print(a.add(b));
    }*/
   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        boolean flag = true;
        for (int i = 0; i < input.length(); i++) {
            String temp = input.substring(i, i + 1);
            if (input.length() - input.replace(temp, "").length() == 1) {
                System.out.println(temp);
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println(-1);
        }


    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int tarNum = in.nextInt();
        int a = 0;
        int b = tarNum;
        for(int i= 2; i < tarNum; i++){
            if(isSusu(i)){
                if (isSusu(tarNum - i)){
                    int temp = tarNum - i;
                    if(Math.abs(temp - i) < b-a){
                        a =(Math.min(i, temp));
                        b = (Math.max(i, temp));
                    }


                }
            }
        }
        System.out.println(a);
        System.out.println(b);

    }

    public static boolean isSusu(int a){
        boolean flag = true;
        for(int i = 2; i <= Math.sqrt(a);i++) {
            if (a % i == 0) {
                return false;
            }
        }
        return flag;
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();

        System.out.println(jieCheng(m+1)/(jieCheng(m-n)*jieCheng(n)*jieCheng(n)));
    }

    public static int jieCheng(int a){
        if(a <= 0){
            return 1;
        }
        else {
            return a * jieCheng(a-1);
        }
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int length = Integer.parseInt(in.nextLine());
        String tar = "";
        Double tarRa = 0.0;
        for(int i = 0; i< str.length() - length;i++){
            String temp = str.substring(i,i+length);
            Double tempCon = length - temp.replace("C", "")
                    .replace("G", "").length()*1.0;

            if(tarRa< tempCon/length){
                tarRa = tempCon/length;
                tar = temp;
            }

        }
        System.out.println(tar);
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = Integer.parseInt(in.nextLine());
        String oper = in.nextLine();
        int[] songsPage = new int[Math.min(4, count)];
        int index = 1;
        for (int i = 0; i < count; i++) {
            songsPage[i] = i + 1;
        }

        for (int i = 0; i < oper.length(); i++) {
            String op = oper.substring(i, i + 1);
            if (op.equals("U")) {
                if (index == 1) {
                    index = count;
                    if (count > 4) {
                        for (int j = 0, k = 3; j < 4; j++, k--) {
                            songsPage[j] = index - k;
                        }
                    }


                } else {
                    index--;
                    if (count > 4) {
                        if (index < songsPage[0]) {
                            for (int j = 0, k = index; j < 4; j++, k++) {
                                songsPage[j] = k;
                            }
                        }
                    }

                }
            } else {
                if (index == count) {
                    index = 1;
                    if (count > 4) {
                        for (int j = 0; j < 4; j++) {
                            songsPage[j] = j + 1;
                        }
                    }
                } else {
                    index++;
                    if (count > 4) {
                        if (index > songsPage[3]) {
                            for (int j = 0, k = 3; j < 4; j++, k--) {
                                songsPage[j] = index - k;
                            }
                        }
                    }

                }

            }
        }

        for (int i = 0; i < songsPage.length; i++) {
            System.out.print(songsPage[i] + " ");
        }
        System.out.print("\n" + index);

    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        if(a.length() > b.length()){
            String temp = a;
            a = b;
            b= temp;
        }
        String tar ="";
        int maxL = Integer.MIN_VALUE;
        for(int i= 0; i< a.length();i++){
            for(int j= i+1; j< a.length();j++){
                String temp = a.substring(i,j);
                int len = b.length()-b.replaceFirst(temp, "").length();
                if( len > maxL){
                    maxL = len;
                    tar = temp;
                }
            }
        }
        System.out.println(tar);
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] keyWordss = {"reset", "reset board", "board add", "board delete", "reboot backplane",
                "backplane abort", "he he"
        };
        String[] keyOprs = {"reset what", "board fault", "where to add", "no board at all", "impossible",
                "install first", "unknown command"
        };

        while (in.hasNextLine()) {
            String str = in.nextLine();
            if (str == null || "".equals(str.trim())) {
                continue;
            }
            int count = 0;
            int oprIndex = 6;
            for (int i = 0; i < keyWordss.length; i++) {
                //命令完全匹配
                if (str.equals(keyWordss[i])) {
                    oprIndex = i;
                    count++;
                    break;
                }
                //单关键字命令匹配
                if (!str.contains(" ") && !keyWordss[i].contains(" ")) {
                    if (keyWordss[i].substring(0, str.length()).equals(str)) {
                        count++;
                        oprIndex = i;
                    }
                }
                //多关键字命令匹配
                if (str.contains(" ") && keyWordss[i].contains(" ")) {
                    boolean flag = false;
                    String[] strArr = str.split(" ");
                    String[] keyArr = keyWordss[i].split(" ");
                    if (strArr.length == keyArr.length) {
                        for (int j = 0; j < strArr.length; j++) {
                            String singleIn = strArr[j];
                            String singleKey = keyArr[j];
                            if(singleIn.length() <singleKey.length()){
                                //每个关键字进行匹配
                                if (!singleIn.equals(singleKey) &&
                                        !singleKey.substring(0, singleIn.length()).equals(singleIn)) {
                                    flag= false;
                                    break;
                                }
                                flag = true;
                            }


                        }
                    }
                    if (flag) {
                        oprIndex = i;
                        count++;
                    }
                }
            }

            if (count == 1) {
                System.out.println(keyOprs[oprIndex]);
            }
            else {
                System.out.println(keyOprs[6]);
            }
        }
    }*/
    //记录数字
    /*static int[] num = new int[4];
    //记录数字是否被使用
    static boolean[] juge = new boolean[4];

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        for (int i = 0; i < 4; i++) {
            num[i] = scan.nextInt();

        }
        System.out.println(dfs(0, 0));


    }

    private static boolean dfs(float result, int use) {
        //递归终止条件，计算值为24点且使用了四个数
        if (result == Float.valueOf(24) && use == 4) {
            return true;
        }

        for (int i = 0; i < 4; i++) {
            //判断第i个数字是否被使用
            if (!juge[i]) {
                //标记该数被使用
                juge[i] = true;
                //递归判断是否符合条件
                if (dfs(result + num[i], use + 1) ||
                        dfs(result - num[i], use + 1) ||
                        dfs(result * num[i], use + 1) ||
                        dfs(result / num[i], use + 1)) {
                    //符合条件返回true
                    return true;
                } else {
                    //回溯时将值标记为未使用（false）
                    juge[i] = false;
                }


            }
        }
        //未找到返回false
        return false;
    }*/

    /*static class User {
        String name;
        int score;

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getScore() {
            return score;
        }

        public void setScore(int score) {
            this.score = score;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int count = Integer.parseInt(in.next());
        String order = in.next();
        List<User> ulist = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            User user = new User();
            user.setName(in.next());
            user.setScore(Integer.parseInt(in.next()));
            ulist.add(user);
        }
        if ("0".equals(order)) {
            ulist.sort((o1,o2) -> Integer.compare(o2.getScore(),o1.getScore()));
        } else {
            ulist.sort((o1,o2) -> Integer.compare(o1.getScore(),o2.getScore()));
        }
        for (User user : ulist) {
            System.out.println(user.getName()+" "+user.getScore());
        }
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int[][] arr1 = new int[a][b];
        int[][] arr2 = new int[b][c];
        int[][] resArr =new int[a][c];
        for(int i=0; i<arr1.length;i++){
            for (int j =0; j<arr1[i].length;j++){
                arr1[i][j] = in.nextInt();
            }
        }
        for(int i=0; i<arr2.length;i++){
            for (int j =0; j<arr2[i].length;j++){
                arr2[i][j] = in.nextInt();
            }
        }
        for(int i=0; i<resArr.length;i++){
            for (int j =0; j<resArr[i].length;j++){
                for(int k = 0;k< arr2.length;k++){
                    resArr[i][j] += arr1[i][k]*arr2[k][j];
                }
                System.out.println(resArr[i][j] +" ");
            }
            System.out.println();
        }

    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String ll = in.nextLine();
            int n = Integer.parseInt(ll);
            int[][] juzhen = new int[n][2];
            for (int i= 0; i < n; i++) {
                String[] temp = in.nextLine().split(" ");
                juzhen[i][0] = Integer.parseInt(temp[0]);
                juzhen[i][1] = Integer.parseInt(temp[1]);
            }
            String faze = in.nextLine();

            System.out.println(function(juzhen, faze));
        }
    }
    public static int function(int[][] juzhen, String yusuan) {
        int result = 0;
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < yusuan.length(); i++) {
            if (yusuan.charAt(i) == '(') {

            } else if (yusuan.charAt(i) == ')') {
                int[] lastjuzhen = stack.pop();
                int[] nearjuzhen = stack.pop();
                result = result + lastjuzhen[0] * lastjuzhen[1] * nearjuzhen[0];
                stack.push(new int[] {nearjuzhen[0], lastjuzhen[1]});

            } else {
                stack.push(juzhen[yusuan.charAt(i) - 'A']);
            }
        }
        return result;
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case

            String pattern = in.nextLine();
            String target = in.nextLine();
            String p_new = pattern.replace("*", "[a-zA-Z0-9]*").
                    replace("?", "[a-zA-Z0-9]?").
                    replace("[a-zA-Z0-9]*[a-zA-Z0-9]*[a-zA-Z0-9]*", "[a-zA-Z0-9]{0,3}").
                    replace("[a-zA-Z0-9]*[a-zA-Z0-9]*", "[a-zA-Z0-9]{0,2}").toUpperCase();

            System.out.println(target.toUpperCase().matches(p_new));
        }
    }*/
   /* public static void main(String[] args) {
        for (int i = 0; i <= 20; i++) {
            for (int j = 0; j <= 100 - 5*i ;j++){
                int num = (100 - 5*i - 3*j) * 3;
                if(num >= 0 && i + j+num ==100){
                    System.out.println(i+" " + j +" "+num);;
                }

            }
        }
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println(getDays(in.nextInt(), in.nextInt(), in.nextInt()));
    }

    public static  int getDays(int year,int month,int day){
        int sum =0;
        boolean isRunYear = false;
        if((year %4 ==0 && year % 100 !=0) || year % 400 ==0){
            isRunYear = true;
        }
        int[] monthDay = {31,28,31,30,31,30,31,31,30,31,30,31};
        if(isRunYear){
            monthDay[1] = 29;
        }
        for (int  i =0 ;i < month -2; i++){
            sum+= monthDay[i];
        }
        return sum+day;
    }*/


    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        List<String> list = new ArrayList<>();
        inserList(list, input);
        System.out.println(list.size());
        for (String s : list) {
            System.out.println(s);
        }
    }
    */

    /**
     * 保存字符串
     *
     * @param list
     * @param s
     *//*
    public static void inserList(List<String> list, String input) {
        if (!" ".equals(input)) {
            if ( input.contains("\"")) {
                //获取第一个“字符位置
                int index = input.indexOf("\"");
                String subAfter = input.substring(0, index);
                inserList(list, subAfter.trim());
                input = input.substring(index + 1, input.length());
                //获取第二个“字符位置
                index = input.indexOf("\"");
                list.add(input.substring(0, index));
                //判断是否为最后一个“
                if (index != input.length() - 1) {
                    input = input.substring(index + 1, input.length());
                    inserList(list, input.trim());
                }
            } else {
                if (!"".equals(input) && input != null) {
                    if (input.contains(" ")) {
                        String[] arr = input.split(" ");
                        for (String string : arr) {
                            list.add(string);
                        }
                    } else {
                        list.add(input);
                    }
                }
            }
        }

    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        int maxlen = Integer.MIN_VALUE;
        if (s.length() > t.length()) {
            String temp = s;
            s = t;
            t = temp;
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                String temp = s.substring(i, j);
                int a = t.length() - t.replaceFirst(temp, "").length();
                maxlen = Math.max(maxlen, a);
            }
        }
        System.out.println(maxlen);
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int total = 0;
        int first = -1;
        while ((double)total != Math.pow(num, 3)){
            total = 0;
            first +=2;
            int copyFirst = first;
            for (int i = 0; i< num; i++){
                total += copyFirst;
                copyFirst +=2;
            }
        }
        if(num == 1){
            System.out.println(first);
        }
        else {
            System.out.print(first +"+");
            for (int i = 1; i< num; i++){
                if( i != num -1){
                    first +=2;
                    System.out.print(first +"+");
                }
                else {
                    System.out.print(first+2  );
                }
            }
        }

    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Set<Integer> list = new HashSet<>();
        int a1 = in.nextInt();
        for (int i = 0; i < a1; i++) {
            list.add(in.nextInt());
        }
        a1 =in.nextInt();
        for (int i = 0; i < a1; i++) {
            list.add(in.nextInt());
        }
        List<Integer> collect = list.stream().sorted((o1, o2) -> Integer.compare(o1, o2)).collect(Collectors.toList());
        for (Integer i : collect) {
            System.out.print(i);
        }
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String t = in.nextLine();
        boolean flag = true;
        for(int i = 0; i< s.length();i++){
            int a = t.indexOf(s.indexOf(i));
            if(a< 0 ){
                flag= false;
            }
        }
        System.out.println(flag);
    }*/

    /*static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] input = in.nextLine().split("/");
        long a = Long.parseLong(input[0]);
        long b = Long.parseLong(input[1]);
        clac(a, b);
        String temp = sb.toString();
        System.out.println(temp.substring(0,temp.length()-1));
    }

    private static void clac(long a, long b) {
        if (a == 1) {
            sb.append("1/").append(b).append("+");
            return;
        }
        if (b % a == 0) {
            sb.append("1/").append(b / a).append("+");
            return;
        }
        long c = (b / a) + 1;
        sb.append("1/").append(c).append("+");

        clac(a - b % a, b * c);
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        int count =0;
        int lowCount = 0;
        char[] ch = input.toCharArray();
        for (char c : ch) {
            if (Character.isLowerCase(c)){
                lowCount ++;
            }
            if (Character.isLetter(c)){
                count ++;
            }

        }
        System.out.println(count - lowCount);
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] ch = in.nextLine().toCharArray();
        int maxLe = 0;
        for (int i = 0; i < ch.length; i++) {
            for (int j = i + 1; j < ch.length; j++) {
                int le = j - i + 1;
                boolean flag = false;
                int begin = i;
                int end = j;
                if (ch[i] == ch[j]) {
                    while (end - begin > 0) {
                        begin++;
                        end--;
                        if (ch[begin] != ch[end]) {
                            flag = false;
                            break;
                        }
                        else {
                            flag = true;
                        }
                    }
                }
                if(flag){
                    maxLe = Math.max(maxLe, le);
                }

            }
        }
        if (ch.length == 1) {
            maxLe = Math.max(maxLe, 1);
        }
        System.out.println(maxLe);
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String binary = Integer.toBinaryString(in.nextInt());
        int maxLe = 0;
        int count = 0;
        char[] ch = binary.toCharArray();
        for (char c : ch) {
            if(c == '1'){
                count++;
            }
            else {
                maxLe = Math.max(maxLe, count);
                count = 0;

            }
        }
        System.out.println(maxLe);
    }*/

    /*static int[] scores = {90, 80, 70, 60, 50, 25, 0};
    static String[] name = {"VERY_SECURE", "SECURE", "VERY_STRONG", "STRONG", "AVERAGE", "WEAK", "VERY_WEAK"};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        int score = 0;
        //密码长度
        if (input.length() <= 4) {
            score += 5;
        } else if (input.length() >= 8) {
            score += 25;
        } else {
            score += 10;
        }
        //字母
        if (input.matches(".*[A-Z].*[a-z].*") || input.matches(".*[a-z].*[A-Z].*")) {
            score += 20;
        } else if (input.matches(".*[A-Z].*") || input.matches(".*[a-z].*")) {
            score += 10;
        }
        //数字
        if (input.matches(".*\\d.*\\d.*")) {
            score += 20;
        } else if (input.matches(".*[0-9].*")) {
            score += 10;
        }
        //符号
        if (input.matches(".*[^A-Za-z0-9].*[^A-Za-z0-9].*")) {
            score += 25;
        } else if (input.matches(".*[^A-Za-z0-9].*")) {
            score += 10;
        }
        //奖励
        if (input.matches(".*[^A-Za-z0-9].*") && input.matches(".*[A-Z].*") &&
                input.matches(".*[a-z].*") &&
                input.matches(".*[0-9].*")) {
            score += 5;
        } else if (input.matches(".*[^A-Za-z0-9].*") && (input.matches(".*[A-Z].*") ||
                input.matches(".*[a-z].*")) &&
                input.matches(".*[0-9].*")) {
            score += 3;
        } else if ((input.matches(".*[A-Z].*") ||
                input.matches(".*[a-z].*")) &&
                input.matches(".*[0-9].*")) {
            score += 2;
        }
        for (int i = 0; i < scores.length; i++) {
            if (score >= scores[i]) {
                System.out.println(name[i]);
                break;
            }
        }
    }*/

    /*public static String nums="3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER";
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] input = in.nextLine().split("-");
        String[] fch = input[0].split(" ");
        String[] cch = input[1].split(" ");
        if(input[0].contains("joker") && input[0].contains("JOKER") ){
            System.out.println(input[0]);
        }
        else if(input[1].contains("joker") && input[1].contains("JOKER")){
            System.out.println(input[1]);
        }
        else {
            //判断两手牌都是 单个，对子，三个，四个，顺子
            if(fch.length == cch.length){
                int index1 = nums.indexOf(fch[0]);
                int index2 = nums.indexOf(cch[0]);
                if(index2 >index1){
                    System.out.println(input[1]);
                }
                else if(index2 < index1) {
                    System.out.println(input[0]);
                }
                else {
                    System.out.println("ERROR");
                }
            }
            //两手牌数量不一致，
            else {
                if(fch.length == 4){
                    System.out.println(input[0]);
                }
                else if(cch.length == 4){
                    System.out.println(input[1]);
                }
                else {
                    System.out.println("ERROR");
                }
            }
        }


    }*/
   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        String[] inArr = input.split("\\.");
        boolean flag = true;
        for (String s : inArr) {
            try {
                int a = Integer.parseInt(s);
                if (a < 0 || a > 255) {
                    flag = false;
                    break;
                }
            } catch (Exception e) {
            } finally {
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int xlen = in.nextInt() + 1;
        int ylen = in.nextInt() + 1;
        int[][] nums = new int[xlen][ylen];

        for (int i = 0; i < xlen; i++) {
            for (int j = 0; j < ylen; j++) {
                if (i == 0 || j == 0) {
                    nums[i][j] = 1;
                } else {
                    nums[i][j] = nums[i - 1][j] + nums[i][j - 1];
                }

            }
        }

        System.out.println(nums[xlen - 1][ylen - 1]);
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        List<String> list = new ArrayList<>();
        int maxl = 0;
        char[] ch = str.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            int count = 0;
            int index = i;
            while (index < str.length() && Character.isDigit(ch[index++])) {
                count++;
            }
            if (count != 0) {
                list.add(str.substring(i, i+count));
                i += count;
            }
            maxl = Math.max(maxl, count);
        }
        for (String s : list) {
            if (s.length() == maxl) {
                System.out.print(s);
            }
        }
        System.out.print("," + maxl);
    }*/

//    public static boolean[] visited;
//
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int count = in.nextInt();
//        List<Integer> alist = new ArrayList<>();
//        List<Integer> blist = new ArrayList<>();
//        List<Integer> templist = new ArrayList<>();
//        for (int i = 0; i < count; i++) {
//            int a = in.nextInt();
//            if (a % 5 == 0) {
//                alist.add(a);
//            } else if (a % 3 == 0) {
//                blist.add(a);
//            } else {
//                templist.add(a);
//            }
//        }
//        //分别计算a、b数组元素和
//        int acount = alist.stream().reduce(0, (a1, a2) -> a1 + a2);
//        int bcount = blist.stream().reduce(0, (b1, b2) -> b1 + b2);
//        if (templist.size() == 0) {
//            if (acount == bcount) {
//                System.out.println("true");
//            } else {
//                System.out.println("false");
//            }
//        } else {
//            visited = new boolean[templist.size()];
//            dfs(templist, 0, acount - bcount);
//        }
//    }
//
//    public static boolean dfs(List<Integer> list, int times, int total) {
//        if (times == list.size()) {
//            return total == 0;
//        }
//        return dfs(list, times + 1, total + list.get(times))
//                || dfs(list, times + 1, total - list.get(times));
//    }
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<String, Integer> map = new LinkedHashMap<>();
        in.nextLine();

        String names = in.nextLine();
        String[] nameArr = names.split(" ");
        for (String s : nameArr) {
            map.put(s, 0);
        }

        in.nextLine();
        String[] tpNames = in.nextLine().split(" ");
        int incount = 0;
        for (String tpName : tpNames) {
            if (map.keySet().contains(tpName)) {
                map.put(tpName, map.get(tpName) + 1);
            } else {
                incount++;
            }
        }
        map.put("Invalid", incount);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }

    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine().trim();
        StringBuilder sb = new StringBuilder(input);
        char[] ch = input.toCharArray();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < ch.length; i++) {
            boolean flag = false;
            int index = i;
            while (index < ch.length && Character.isDigit(ch[index++])) {
                flag = true;
            }
            if (flag) {
                list.add(i);
                if (index == input.length()) {
                    list.add(index);
                } else {
                    list.add(index - 1);
                }

                i = index - 1;

            }

        }
        for (int i = list.size() - 1; i >= 0; i--) {
            sb.insert(list.get(i), "*");
        }
        System.out.println(sb.toString());
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int total = 0;
        int fcount = 0;
        int zcount = 0;

        for (int i = 0; i < count; i++) {
            int a = in.nextInt();
            if (a < 0) {
                fcount++;
            }
            if (a > 0) {
                total += a;
                zcount++;
            }
        }
        System.out.println(fcount + " " + (total * 1.0) / zcount);

    }*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int count = 0;
        for(int i = 1; i<= a;i++){
            if (isZss(a)){
                count++;
            }
        }
        System.out.println(count);
    }


    public static boolean isZss(int a){
        String aa = String.valueOf(a*a);
        String as = String.valueOf(a);
        if(aa.equals(as) || aa.substring(aa.length() - as.length(),aa.length()).equals(as)){
            return true;
        }
        else {
            return false;
        }
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            list.add(in.nextInt());
        }
        int order = in.nextInt();
        if (order == 0) {
            list = list.stream().sorted((o1, o2) -> Integer.compare(o1, o2)).collect(Collectors.toList());
        } else {
            list = list.stream().sorted((o1, o2) -> Integer.compare(o2, o1)).collect(Collectors.toList());

        }
        for (Integer i : list) {
            System.out.print(i + " ");
        }
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] input = in.nextLine().toCharArray();
        StringBuilder sb = new StringBuilder();
        int[] ch = new int[128];
        for (int i = 0; i < input.length; i++) {
            ch[input[i]]++;
        }
        int max = 0;
        for (int i = 0; i < ch.length; i++) {
            max = Math.max(max, ch[i]);
        }
        while (max != 0) {
            for (int i = 0; i < ch.length; i++) {
                if (ch[i] == max) {
                    sb.append((char) i);
                }
            }
            max--;
        }
        System.out.println(sb.toString());
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int[] mhz = new int[count];
        int[] lefth = new int[count];
        Arrays.fill(lefth, 1);
        for (int i = 0; i < count; i++) {
            mhz[i] = in.nextInt();
        }
        for (int i = 0; i < count; i++) {
            for (int j = i + 1; i < count; j++) {
                if (mhz[j] > mhz[i]) {
                    lefth[j] = Math.max(lefth[j], lefth[i] + 1);
                }
            }
        }
        int max = 0;
        for (int i = 0; i < count; i++) {
            max =Math.max(max, lefth[i]);
        }
        System.out.println(max);
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int temp = 1;
        for (int i = 2; i < a && i < b; i++) {
            while (a % i == 0 || b % i == 0) {
                temp *= i;
                a /= i;
                b /= i;
            }
        }
        System.out.println(temp * a * b);
    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] ch = in.nextLine().toCharArray();
        Set<Character> set = new HashSet<>();
        for (char c : ch) {
            set.add(c);
        }
        System.out.println(set.size());

    }*/
    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //气球数量
        int count = Integer.parseInt(in.nextLine());
        //气球颜色
        char[] colors = in.nextLine().toCharArray();
        //染色时间
        int[] cost = new int[count];
        String[] costStr = in.nextLine().split(" ");
        for (int i = 0; i < count; i++) {
            cost[i] = Integer.parseInt(costStr[i]);
        }

        //处理不需要染色情况,000,01,012,
        boolean noRs = true;
        int rsCount = 0;
        for (int i = 0; i < count - 1; i++) {
            if (colors[i] != colors[i + 1]) {
                noRs = false;
                rsCount++;
            }
        }
        if (noRs || rsCount == 1 || (rsCount == 2 && colors[0] != colors[count - 1])) {
            System.out.println(0);
            return;
        }
        // 预处理前缀和数组：pre[i][c] 表示前i个气球染成颜色c的总成本
        long[][] pre = new long[count + 1][3];
        for (int i = 0; i < count; i++) {
            for (int c = 0; c < 3; c++) {
                pre[i + 1][c] = pre[i][c] + getCost(colors[i], c, cost[i]);
            }
        }
        // 所有可能的颜色排列组合（三颜色全排列）
        long minTotal = getMinTotal(n, pre);

        System.out.println(minTotal);
        in.close();
    }

    // 计算将原始颜色originalColor染成目标颜色targetColor的成本
    private static long getCost(char originalColor, int targetColor, int cost) {
        int original = originalColor - '0';
        return (original == targetColor) ? 0 : cost;
    }

    private static long getMinTotal(int count, long[][] pre) {
        int[][] permutations = {
                {0, 1, 2}, {0, 2, 1},
                {1, 0, 2}, {1, 2, 0},
                {2, 0, 1}, {2, 1, 0}
        };

        long minTotal = Long.MAX_VALUE;

        for (int[] perm : permutations) {
            long minPrefix = Long.MAX_VALUE;
            for (int split2 = 2; split2 <= count; split2++) {
                int split1 = split2 - 1;

                long prefix = pre[split1][perm[0]] - pre[split1][perm[1]];
                minPrefix = Math.min(minPrefix, prefix);


                long total = minPrefix + pre[split2][perm[1]] + pre[count][perm[2]] - pre[split2][perm[2]];
                minTotal = Math.min(minTotal, total);
            }
        }
        return minTotal;
    }*/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] ab = in.nextLine().trim().split(" ");
        int a = Integer.parseInt(ab[0]);
        int b = Integer.parseInt(ab[1]);
        String[] nums = new String[a];
        for (int i = 0; i < a; i++) {
            nums[i] = in.nextLine().trim();
        }
        int count = 0;
        for (int i = 0; i <= a; i++) {
            count = Math.max(count, getCount(nums, i, a, b));
        }

        System.out.println(count);
    }

    public static int getCount(String[] nums, int index, int a, int b) {
        int count = 0;
        for (int i = 0; i < b; i++) {
            boolean flag = true;
            for (int j = 0; j < a; j++) {
                if (index == a) {
                    if (nums[j].charAt(i) != '1') {
                        flag = false;
                        continue;
                    }
                } else if ((j != index && nums[j].charAt(i) != '1')
                        || (j == index && nums[j].charAt(i) != '0')) {
                    flag = false;
                    continue;
                }
            }
            if (flag) {
                count++;
            }
        }
        return count;

    }


}




